package LeetCode;

/**
 * description:
 * author:张腾
 * date:2021-06-08
 */

/**
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串
 */
public class leetcode647 {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans=0;

        for (int i=1;i<s.length()-1;i++){
            for (int j=0;j<=i;j++){
                if (s.charAt(i)==s.charAt(j) && (i-j<2 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    ans ++;
                }
            }
        }
        return ans;
    }
}
